/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30/FONT#11=ZERO30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓α␈↓ ∧RFORMALIZATION OF OCKHAM'S RAZOR

␈↓ α∧␈↓␈↓ αTResearch␈α
in␈α
artificial␈αintelligence␈α
involves␈α
two␈α
components␈αwhich␈α
may␈α
be␈αcalled␈α
␈↓↓epistemology␈↓
␈↓ α∧␈↓and␈α⊃␈↓↓heuristics.␈↓␈α∩Heuristics␈α⊃deals␈α∩with␈α⊃search␈α⊃of␈α∩spaces␈α⊃of␈α∩possibilities,␈α⊃with␈α∩pattern␈α⊃matching,
␈↓ α∧␈↓planning␈α
and␈α
many␈α
other␈α
topics.␈α
 The␈α
epistemological␈α
part␈α
of␈α
AI,␈α
which␈α
seems␈α
to␈α
be␈α
contiguous
␈↓ α∧␈↓with␈αsome␈αof␈αthe␈αepistemological␈αproblems␈αof␈αphilosophy,␈αis␈αconcerned␈αwith␈αwhat␈αare␈α
the␈αgeneral
␈↓ α∧␈↓facts␈αof␈αthe␈αcommon␈αsense␈αworld␈αand␈αhow␈αthey␈αmay␈αbe␈αrepresented␈αin␈αthe␈αmemory␈αof␈αa␈αcomputer,
␈↓ α∧␈↓how␈α
the␈α
particular␈α
facts␈α
of␈α
a␈α
situation␈α
are␈α
consequences␈α
of␈α
observation␈α
or␈α
communication␈αand␈α
how
␈↓ α∧␈↓they␈α
may␈α
be␈αrepresented,␈α
and␈α
with␈α
the␈αrules␈α
of␈α
inference␈α
or␈αconjecture,␈α
whereby␈α
an␈α
organism␈αor
␈↓ α∧␈↓machine may justifiably go from premisses to conclusions.

␈↓ α∧␈↓␈↓ αTThe␈α∞work␈α∞described␈α
here␈α∞arises␈α∞in␈α
trying␈α∞to␈α∞make␈α
computers␈α∞reason,␈α∞i.e.␈α∞draw␈α
conclusions
␈↓ α∧␈↓from␈α
facts,␈α
in␈α
common␈αsense␈α
situations.␈α
 An␈α
early␈αapproach␈α
(McCarthy␈α
1960),␈α
which␈α
had␈αpartial
␈↓ α∧␈↓success␈α∞and␈α∞whose␈α∞ideas␈α∞have␈α∂led␈α∞to␈α∞other␈α∞approaches,␈α∞is␈α∂to␈α∞represent␈α∞facts␈α∞about␈α∞the␈α∂world␈α∞in
␈↓ α∧␈↓general␈α
and␈α
about␈α
particular␈α
situations␈α
by␈α
sentences␈α
of␈α
some␈α
system␈α
of␈α
mathematical␈α
logic.␈α First
␈↓ α∧␈↓order␈αlanguages␈αhave␈αbeen␈αmainly␈αused,␈αbecause␈αthey␈αare␈αbest␈αunderstood␈αand␈αbecause␈αset␈αtheory,
␈↓ α∧␈↓which is as powerful as any system of logic, can be formulated as a first order theory.

␈↓ α∧␈↓␈↓ αTWhile␈α⊂the␈α⊂facts␈α⊂of␈α∂particular␈α⊂situations␈α⊂are␈α⊂often␈α∂conveniently␈α⊂represented␈α⊂in␈α⊂first␈α∂order
␈↓ α∧␈↓formalisms,␈α∞it␈α
eventually␈α∞became␈α∞clear␈α
that␈α∞not␈α∞all␈α
human␈α∞reasoning,␈α∞and␈α
not␈α∞all␈α∞reasoning␈α
that
␈↓ α∧␈↓computers␈α
must␈α
do␈α
to␈α
behave␈α
intelligently,␈α
can␈α
be␈αmodelled␈α
by␈α
the␈α
rules␈α
of␈α
inference␈α
of␈α
a␈αsystem␈α
of
␈↓ α∧␈↓mathematical␈αlogic.␈α
 It␈αbecomes␈αnecessary␈α
to␈αsupplement␈αthe␈α
valid␈α␈↓↓rules␈αof␈α
inference␈↓␈αof␈α
logic␈αwith
␈↓ α∧␈↓␈↓↓rules␈α⊗of␈α↔conjecture␈↓.␈α⊗ However,␈α⊗it␈α↔turns␈α⊗out␈α⊗that␈α↔some␈α⊗of␈α⊗these␈α↔rules␈α⊗of␈α↔conjecture␈α⊗admit
␈↓ α∧␈↓mathematical formalization as precise as that of the rules of inference of logic.

␈↓ α∧␈↓␈↓ αTThe␈α
problem␈α
is␈α
that␈α
we␈αoften␈α
draw␈α
conclusions␈α
in␈α
the␈αabsence␈α
of␈α
certain␈α
facts␈α
that␈αwe␈α
would
␈↓ α∧␈↓not␈αdraw␈αin␈αtheir␈αpresence.␈α In␈αparticular,␈αwe␈αoften␈αpresume␈αthat␈αthe␈αobjects␈αexplicitly␈αmentioned,
␈↓ α∧␈↓together␈αwith␈αthe␈αobjects␈αwhose␈αexistence␈αcan␈αbe␈αdeduced,␈αare␈αall␈αthe␈αobjects␈αthere␈αare␈αof␈αa␈αgiven
␈↓ α∧␈↓kind.␈α This␈αis␈αa␈αkind␈α
of␈αOckham's␈αrazor,␈αalthough,␈αbecause␈αof␈α
a␈αchange␈αin␈αthe␈αformalism␈α
I␈αshall
␈↓ α∧␈↓discuss, the parallel is less striking than when the title of the lecture was chosen.

␈↓ α∧␈↓␈↓ αTThe␈α⊗phenomenon␈α⊗that␈α⊗new␈α↔facts␈α⊗invalidate␈α⊗correctly␈α⊗deduced␈α⊗conclusions␈α↔violates␈α⊗a
␈↓ α∧␈↓monotonicity␈αproperty␈α
posessed␈αby␈αall␈α
systems␈αof␈αmathematical␈α
logic.␈α Symbolically␈α
␈↓↓monotonicity␈↓␈αis
␈↓ α∧␈↓expressed by

␈↓ α∧␈↓↓␈↓ β∧A ␈↓πr␈↓↓ p
␈↓ α∧␈↓↓␈↓ β∧A ⊂ B
␈↓ α∧␈↓↓␈↓ β∧      
␈↓ α∧␈↓↓␈↓ β∧B ␈↓πr␈↓↓ p


␈↓ α∧␈↓Here␈α
␈↓↓A␈↓␈α
and␈α
␈↓↓B␈↓␈αare␈α
sets␈α
of␈α
sentences,␈α
␈↓↓p␈↓␈αis␈α
a␈α
sentence,␈α
and␈α
␈↓↓A ␈↓πr␈↓↓ p␈↓␈αis␈α
read␈α
␈↓↓"p␈α
is␈α
logically␈αdeducible␈α
from
␈↓ α∧␈↓↓A"␈↓.␈α The␈αpoint␈αis␈αthat␈αif␈α␈↓↓p␈↓␈αis␈αa␈αlogical␈αconsequence␈αof␈αa␈αcollection␈α␈↓↓A␈↓␈αof␈αsentences␈αand␈α␈↓↓B␈↓␈αis␈αa␈αmore
␈↓ α∧␈↓inclusive␈αcollection␈αof␈αsentences,␈αthen␈α␈↓↓p␈↓␈αis␈αa␈αlogical␈αconsequence␈αof␈α␈↓↓B.␈↓␈αIndeed␈αthe␈αproof␈αof␈α␈↓↓p␈↓␈αfrom
␈↓ α∧␈↓␈↓↓A␈↓␈α∞will␈α
also␈α∞serve␈α∞as␈α
a␈α∞proof␈α
of␈α∞␈↓↓p␈↓␈α∞from␈α
␈↓↓B.␈↓␈α∞Monotonicity␈α
is␈α∞a␈α∞characteristic␈α
of␈α∞all␈α∞present␈α
logical
␈↓ α∧␈↓systems, and maybe all possible logical systems that do only reasoning guaranteed to be correct.

␈↓ α∧␈↓␈↓ αTThat␈αmuch␈αordinary␈αreasoning␈αis␈αnot␈αmonotonic␈αis␈αbest␈αseen␈αwith␈αthe␈αaid␈αof␈αan␈αexample.␈α I
␈↓ α∧␈↓know␈α
that␈α
you␈α
own␈αa␈α
car,␈α
and␈α
I␈αconclude␈α
that␈α
it␈α
is␈αappropriate␈α
to␈α
ask␈α
you␈αfor␈α
a␈α
ride␈α
to␈αthe␈α
airport.
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓Before␈α⊃asking,␈α⊃however,␈α∩I␈α⊃learn␈α⊃that␈α∩your␈α⊃car␈α⊃is␈α∩being␈α⊃repaired␈α⊃and␈α∩conclude␈α⊃that␈α⊃it␈α∩is␈α⊃not
␈↓ α∧␈↓appropriate.␈α∞ Then␈α∞I␈α∞learn␈α∞that␈α
you␈α∞have␈α∞your␈α∞wife's␈α∞car,␈α
etc.,␈α∞etc.␈α∞ No␈α∞new␈α∞fact␈α∞contradicts␈α
the
␈↓ α∧␈↓previous collection of facts, but each new fact reverses the appropriateness of asking for a ride.

␈↓ α∧␈↓␈↓ αTOne␈α⊂can␈α∂attempt␈α⊂to␈α∂deal␈α⊂with␈α∂this␈α⊂phenomenon␈α∂in␈α⊂various␈α∂ways,␈α⊂and␈α∂perhaps␈α⊂the␈α∂most
␈↓ α∧␈↓congenial␈α⊂to␈α⊃my␈α⊂preconceptions␈α⊃of␈α⊂the␈α⊃preconceptions␈α⊂of␈α⊃this␈α⊂audience␈α⊃would␈α⊂be␈α⊃to␈α⊂introduce
␈↓ α∧␈↓probabilities.␈α For␈αreasons␈αwe␈αshall␈αdiscuss␈αlater,␈αwe␈αdon't␈αbelieve␈αthis␈αmeets␈αthe␈αproblem␈αhead␈αon,
␈↓ α∧␈↓and␈αI␈αshall␈αdiscuss␈αtwo␈αnon-probabilistic␈αapproaches␈αto␈αnon-monotonic␈αreasoning␈αthat␈αhave␈αbeen
␈↓ α∧␈↓taken␈α⊃by␈α⊃researchers␈α⊃in␈α⊃artificial␈α⊃intelligence.␈α⊃ Both␈α⊃approaches␈α⊃are␈α⊃discussed␈α⊃in␈α⊃articles␈α⊃in␈α⊂a
␈↓ α∧␈↓forthcoming␈α⊂issue␈α⊂of␈α⊂the␈α⊂journal␈α⊂␈↓↓Artificial␈α⊂Intelligence␈↓.␈α⊂ See␈α⊂references␈α⊂(McDermott␈α⊂and␈α⊂Doyle
␈↓ α∧␈↓1980), (Reiter 1980) and (McCarthy 1980).

␈↓ α∧␈↓␈↓ αTSuppose␈αwe␈αhave␈αa␈αbinary␈α(say)␈αpredicate␈α␈↓↓P(x,y)␈↓␈αaxiomatized␈αby␈αa␈αsentence␈α␈↓↓Axiom(P).␈↓␈αThe
␈↓ α∧␈↓conjecture␈α
that␈α
␈↓↓P␈↓␈α
applies␈α
to␈α
the␈α
smallest␈α
possible␈α
set␈α
of␈α
pairs␈α
consistent␈α
with␈α
its␈αsatisfying␈α
␈↓↓Axiom(P)␈↓
␈↓ α∧␈↓can be expressed by the schema

␈↓ α∧␈↓␈↓ αT␈↓↓Axiom(␈↓	F␈↓↓) ∧ ∀x y.(␈↓	F␈↓↓(x,y) ⊃ P(x,y)) ⊃ ∀x y.(P(x,y) ⊃ ␈↓	F␈↓↓(x,y))␈↓.

␈↓ α∧␈↓Here ␈↓↓␈↓	F␈↓↓(x,y)␈↓ can be an arbitrary wff with free variables ␈↓↓x␈↓ and ␈↓↓y.␈↓

␈↓ α∧␈↓␈↓ αTAnother␈α∞application␈α∞of␈α∞non-monotonic␈α∞reasoning␈α∞may␈α
be␈α∞used␈α∞to␈α∞express␈α∞the␈α∞idea␈α∞that␈α
␈↓↓it
␈↓ α∧␈↓↓isn't␈αsafe␈αto␈αcross␈αthe␈α
tracks␈αif␈αthere␈αmay␈αbe␈α
a␈αtrain␈αon␈αthem␈↓.␈α Suppose␈α
the␈αpredicate␈α␈↓↓on␈↓␈αused␈αin␈α
the
␈↓ α∧␈↓expression␈α∃␈↓↓on(train,␈↓␈α∃tracks)␈α∃is␈α∃axiomatized␈α⊗by␈α∃␈↓↓Axiom(on).␈↓␈α∃The␈α∃italicized␈α∃statement␈α⊗is␈α∃then
␈↓ α∧␈↓expressed by the schema

␈↓ α∧␈↓␈↓ αT␈↓↓Axiom(␈↓	F␈↓↓) ∧ ␈↓	F␈↓↓(train,tracks) ⊃ ¬safe-to-cross(tracks)␈↓.

␈↓ α∧␈↓Some␈αof␈αthe␈αmathematical␈αproperties␈αof␈αthese␈αmodes␈αof␈αnon-monotonic␈αreasoning␈αas␈αwell␈αas␈αsome
␈↓ α∧␈↓applications to common sense reasoning will be described in the paper.

␈↓ α∧␈↓␈↓ αT References:

␈↓ α∧␈↓␈↓αMcCarthy,␈α_John␈α_(1960)␈↓:␈α→"Programs␈α_with␈α_Common␈α→Sense",␈α_␈↓↓Proceedings␈α_of␈α→the␈α_Teddington
␈↓ α∧␈↓↓Conference on the Mechanization of Thought Processes␈↓, H.M.  Stationery Office, 1960.

␈↓ α∧␈↓␈↓αMcCarthy,␈α⊃John␈α⊃(1980)␈↓:␈α⊃"Circumscription␈α∩-␈α⊃A␈α⊃Form␈α⊃of␈α⊃Non-Monotonic␈α∩Reasoning",␈α⊃␈↓↓Artificial
␈↓ α∧␈↓↓Intelligence␈↓, forthcoming.

␈↓ α∧␈↓␈↓αMcDermott,␈α∃Drew␈α∃and␈α∀Jon␈α∃Doyle␈α∃(1980):␈α∀"Non-Monotonic␈α∃Logic␈α∃I",␈α∃␈↓↓Artificial␈α∀Intelligence␈↓,
␈↓ α∧␈↓forthcoming.

␈↓ α∧␈↓␈↓αReiter, Raymond (1980)␈↓: "A Logic for Default Reasoning", ␈↓↓Artificial Intelligence␈↓, forthcoming.